﻿using System;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Utils;

namespace Algoritmia.Problems.CoinChange
{
    public class GreedyCoinChanger1 : IGreedyCoinChanger
    {
        private readonly Func<IList<int>> _createList;
        private readonly IList<int> _list;

        public GreedyCoinChanger1(IList<int> list, Func<IList<int>> createList = null)
        {
            _list = list;
            _createList = createList ?? (() => AlgoritmiaFactory.Lists<int>.Default);
        }

        #region Implementation of IGreedyCoinChanger

        public IList<int> Change(int Q)
        {
            var x = _createList();
            for (int i = 0; i < _list.Count; i++ )
            {
                x.Add(Q / _list[i]);
                Q = Q% _list[i];
                if (Q == 0)
                {
                    for (int j = i + 1; j < _list.Count; j++ )
                    {
                        x.Add(0);
                    }
                    return x;
                }
            }
            throw new InvalidOperationException("no solution was found");
        }

        #endregion
    }
}
